class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hash1;
        multimap<int, int, greater<int>> hash2;
        for (auto& x : nums) hash1[x]++;
        for (auto& x : hash1) hash2.insert({ x.second, x.first });
        vector<int> ret;
        for (auto& x : hash2) {
            if (k == 0) break;
            ret.push_back(x.second);
            k--;
        }
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> tmp;
    TreeNode* balanceBST(TreeNode* root) {
        getInorder(root);
        return buildBST(0, tmp.size() - 1);
    }
    void getInorder(TreeNode* root)
    {
        if (!root) return;
        getInorder(root->left);
        tmp.push_back(root->val);
        getInorder(root->right);
    }
    TreeNode* buildBST(int left, int right)
    {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;
        TreeNode* node = new TreeNode(tmp[mid]);
        node->left = buildBST(left, mid - 1);
        node->right = buildBST(mid + 1, right);

        return node;


    }
};